/**
 * 找出 100 以内的素数（质数)？
 * 质数是指只能被 1 和它本身整除的自然数
 * eg: 2,3,5,7
 */

class PrimeNumber {
    public static void main(String[] args) {
        getPrimeNumber();
        getPrimeNumber1();
        getPrimeNumber2();
    }

    /**
     * 方法一：反证法
     * 找到从 2 开始到这个数-1 为止,存在约数的自然数，取反即为质数
     */
    private static void getPrimeNumber() {
        // 遍历 100 以内的自然数
        for (int i = 2; i <= 100; i++) {
            // 记录 i 的约数的个数（从 2 开始到 i-1）
            int number = 0;
            // 找质数：从 2 开始到这个数-1 为止，不存在这个自然熟的约数
            for (int j = 2; j < i; j++) {
                // 条件成立，存在约数 number 加 1
                if (i % j == 0) {
                    number++;
                }
            }
            // 条件成立，及 i 是质数
            if (number == 0) {
                System.out.println(i);
            }
        }
    }

    /**
     * 方法二：反证法
     * 表示类型改成，无需关心多少个事关心有没有
     * 找到从 2 开始到这个数-1 为止,存在约数的自然数，取反即为质数
     */
    private static void getPrimeNumber1() {

        // 遍历 100 以内的自然数
        for (int i = 2; i <= 100; i++) {
            // 记录 i 是否有约数（从 2 开始到 i-1）
            boolean isFlag = false;
            // 找质数：从 2 开始到这个数-1 为止，不存在这个自然熟的约数
            for (int j = 2; j < i; j++) {
                // 条件成立，存在约数 isFlag 改为 true
                if (i % j == 0) {
                    isFlag = true;
                }
            }
            // isFlag 为 false 即 i 无约数
            if (isFlag == false) {
                System.out.println(i);
            }
        }
    }

    /**
     * 方法三：优化代码提升性能
     */
    private static void getPrimeNumber2() {

        // 遍历 100 以内的自然数
        for (int i = 2; i <= 100000; i++) {
            // 记录 i 是否有约数（从 2 开始到 i-1）
            boolean isFlag = false;
            // 找质数：从 2 开始到这个数-1 为止，不存在这个自然熟的约数
            for (int j = 2; j <= Math.sqrt(i); j++) {

                // 条件成立，存在约数 isFlag 改为 true
                if (i % j == 0) {
                    isFlag = true;
                    // 只要有就排除，跳出循环寻找下一个
                    break;
                }
            }
            // isFlag 为 false 即 i 无约数
            if (isFlag == false) {
                System.out.println(i);
            }
        }
    }
}